package com.markus.code.剑指offer;

import javax.xml.crypto.dsig.spec.XSLTTransformParameterSpec;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;

/**
 * Author:markusZhang
 * Date:Create in 2020/9/11 16:49
 * todo: 字符串的排列
 */
public class Permutation {
    /**
     * 超出时间限制
     * @param s
     * @return
     */
//    public String[] permutation(String s) {
//        if (s == null || s.length() == 0){
//            return new String[0];
//        }
//        char[] chars = s.toCharArray();
//        List<Character> path = new ArrayList<>();
//        List<List<Character>> ans = new ArrayList<>();
//        boolean []visited = new boolean[chars.length];
//        process(chars,0,path,ans,visited);
//        String[] strings = new String[ans.size()];
//        int index = 0;
//        for (List<Character> an : ans) {
//            StringBuffer sb = new StringBuffer();
//            for (Character character : an) {
//                sb.append(character);
//            }
//            strings[index++] = sb.toString();
//        }
//        return strings;
//    }
//    private void process(char[] chars, int index, List<Character> path,List<List<Character>> ans,boolean[] visited){
//        if (index == chars.length){
//            if (!ans.contains(path)){
//                ans.add(new ArrayList<>(path));
//            }
//            return ;
//        }
//        for (int i=0;i<chars.length;i++){
//            if (!visited[i]){
//                visited[i] = true;
//                path.add(chars[i]);
//                process(chars,index+1,path,ans,visited);
//                path.remove(path.size()-1);
//                visited[i] = false;
//            }
//        }
//    }

    private HashSet<String> set;
    public String[] permutation(String s) {
        if (s == null || s.length() == 0){
            return new String[0];
        }
        this.set = new HashSet<>();
        boolean []visited = new boolean[s.length()];
        process(s,"",visited);
        return set.toArray(new String[set.size()]);
    }
    private void process(String s,String letter,boolean []visited){
        if (s.length() == letter.length()){
            set.add(letter);
            return ;
        }
        for (int i=0;i<s.length();i++){
            if (!visited[i]){
                visited[i] = true;
                process(s,letter+s.charAt(i),visited);
                visited[i] = false;
            }
        }
    }

    public static void main(String[] args) {
        Permutation demo = new Permutation();
        String s = "abc";
        String[] permutation = demo.permutation(s);
        for (String s1 : permutation) {
            System.out.println(s1);
        }
    }
}
